package com.kongge.algorithm.demo;

import com.kongge.algorithm.tree.TreeNode;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构
 * @author kongge
 *
 */
public class TreeContainsSubTree implements IAlgorithm {

	public void execute() {
		TreeNode<Integer> root = TreeNode.createTree(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8});
		TreeNode<Integer> subTree = TreeNode.createTree(new Integer[] {3, 6});
		boolean result = treeHasSubTree(root, subTree);
		System.out.println("root is contains subTree: " + result);
	}

	private boolean treeHasSubTree(TreeNode<Integer> root, TreeNode<Integer> subTree) {
		if (root == null || subTree == null) {
			return false;
		}
		boolean isContains = isContainsSubTree(root, subTree);
		if (!isContains) {
			isContains = treeHasSubTree(root.left, subTree);
		}
		if (!isContains) {
			isContains = treeHasSubTree(root.right, subTree);
		}
		return isContains;
	}
	
	private boolean isContainsSubTree(TreeNode<Integer> root, TreeNode<Integer> subTree) {
		if (subTree == null) {
			return true;
		}
		if (root == null) {
			return false;
		}
		if (root.value != subTree.value) {
			return false;
		}
		return isContainsSubTree(root.left, subTree.left) && isContainsSubTree(root.right, subTree.right);
	}
}
